package com.kevinkk.linklist;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 通过快慢指针的方式，让快指针先走 n 步，领先慢指针，然后快慢指针一起出发
 * 这样等快指针到了链表结尾时，慢指针刚好到了倒数第 n 个的位置
 */

public class RemoveNthNodeFromEndOfList {
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1, head), slow = dummy, fast = dummy;
            for (int i = 0; i < n; i++)
                fast = fast.next;

            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
    }
}
